1. Technical Field
The present invention relates generally to parallel data processing, and more particularly to the use of a dynamic data partitioning scheme for optimal resource utilization in a parallel data processing system.
2. Discussion of Related Art
Data partitioning is a widely used technique in parallel data processing to divide work among many parallel processes or threads. Multiple instances of a dataflow are created (called partitions), each to process some fraction of the overall data set in parallel, thus enabling scalability of the data flow. In recent years, computer systems have been moving in a direction of increasing the number of processor cores and threads, either on a single system or among a group of systems such as a distributed processing system. Data partitioning is one way to take advantage of multi-processor systems by using parallel data processing streams to operate on the partitioned data. This mechanism is used in parallel databases and other parallel data processing engines such as IBM® InfoSphere™ DataStage® to perform high volume data manipulation tasks. (IBM, InfoSphere and DataStage are trademarks of International Business Machines Corporation, registered in many jurisdictions worldwide.)
A popular method for partitioning data is “round robin” partitioning. In this method, each partition is given one unit of data (e.g., a table row or record) at a time in a cycle, like a card dealer distributing cards to players. This method ensures that each partition is given an equal amount of data to processes (except on the last cycle when we may run out of data before the cycle completes). Therefore, the round robin partitioning scheme produces equally balanced data partitions in terms of the amount of data each partition has to process. This system works well if each partition is able to process an equal portion of the data and perform the same amount of work as the other partitions. In some multi-processor systems, however, some partitions may be slower than others, and overall data performance may become gated by the lowest performing partition, thereby leading to system under-utilization and overall decreased throughput.